'lintcode 硬币排成线'

Posted on | In

描述

有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。

请判定 先手玩家 必胜还是必败?

若必胜, 返回 true, 否则返回 false.

样例

输入: 4
输出: true
解释:
先手玩家第一轮拿走一个硬币, 此时还剩三个.
这时无论后手玩家拿一个还是两个, 下一次先手玩家都可以把剩下的硬币拿完.

挑战

O(1) 时间复杂度且O(1) 存储。

思路

因为一次只能拿1个或者2个，所以如果只剩下3个是必输的。所以问题就可以转化成，拿走一次之后，能否剩下3个。这就意味着，若现在有n个硬币，谁先拿走倒数第四个，谁就赢了。于是 Fn = Fn-3，问题就解决了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    /**
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    bool firstWillWin(int n) {
        // write your code here
        if (n == 3 || n == 0) return false;
        else if (n < 3) return true;
        return firstWillWin(n-3);
    }
};
-------------end of filethanks for reading-------------